package com.kavinz.alog.hashtable;

/**
 * <SW-Algorithm> 3.4.1 Insert the keys E A S Y Q U T I O N in that order into
 * an initially empty table of M = 5 lists, using separate chaining. Use the
 * hash function 11 k % M to transform the kth letter of the alphabet into a
 * table index.
 * 
 * @author Kevin Zhao
 * 
 */
public class SeparateChainingHashTable {
	private int M;// hashTable size
	private SymbolTable[] internalStorage;

	public SeparateChainingHashTable(int M) {
		this.M = M;
		internalStorage = new SymbolTable[M];
	}

	public Object get(String key) {
		// get hash value for specified key
		int hash = hash(key);
		//
		SymbolTable symbolTable = internalStorage[hash];
		return symbolTable.get(key);
	}

	public void put(String key, Object value) {
		// get hash value for specified key
		int hash = hash(key);
		// collision resolving-separate chaining
		SymbolTable symbolTable = internalStorage[hash];
		if (symbolTable == null) {
			internalStorage[hash] = symbolTable = new SymbolTable();
		}
		symbolTable.put(key, value);
	}

	/**
	 * convert an string into an unique hash key
	 * 
	 * @param key
	 *            input string
	 * @return hash key
	 */
	private int hash(String key) {
		int R = 6533;
		int hash = 0;
		for (int i = 0; i < key.length(); i++)
			hash = (R * hash + key.charAt(i)) % M;
		return hash;
	}

	public static void main(String[] args) {
		SeparateChainingHashTable hashTable = new SeparateChainingHashTable(5);
		hashTable.put("bafasd", "b");
		hashTable.put("grhae", "g");
		hashTable.put("jdsg", "j");
		hashTable.put("eahq", "e");

		hashTable.put("fsehseg", "fs");
		hashTable.put("faehseg", "fa");
		hashTable.put("cawgq", "c");

		System.out.println(hashTable.get("fsehseg").toString());
	}
}
